# leetcode 1457 二叉树中的伪回文路径


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right


# 版本1， 会超时

class Solution:

    def ispare(self, nums):
        nmap = {}
        for i in nums:
            if i not in nmap:
                nmap[i] = 1
            else:
                nmap[i] += 1
        if len(nums) % 2 == 0:
            for i in nmap:
                if nmap[i] % 2 != 0:
                    return False
            else:
                return True
        else:
            angle = 0
            for i in nmap:
                if nmap[i] % 2 != 0:
                    angle += 1
                    if angle >= 2:
                        return False
            return True

    def pseudoPalindromicPaths (self, root: Optional[TreeNode]) -> int:
        result = []
        path = []
        self.__count = 0
        def travel(node):
            path.append(node.val)
            if (not node.right) and (not node.left):
                # result.append(tuple(path))
                if self.ispare(path):
                    self.__count += 1
            if node.left:
                travel(node.left)
                path.pop()
            if node.right:
                travel(node.right)
                path.pop() 
        if not root:
            return result
        travel(root)
        return self.__count



# 优化版本

class Solution:

    def pseudoPalindromicPaths (self, root: Optional[TreeNode]) -> int:
        st, node = [], root
        ans, path = 0, 0

        while st or node:
            while node:
                path ^= 1 << node.val
                if not node.left and not node.right:
                    ans += path & (path - 1) == 0
                st.append([node, path])
                node = node.left
            node, path = st.pop()
            node = node.right

        return ans
